package com.example.test

import android.util.Log
import java.util.Arrays
import java.util.regex.Matcher
import java.util.regex.Pattern

class SortDemo {

    /**
     * 冒泡
     */
    fun bubbleSort(arr: Array<String>) {
        Log.d("bubble排序开始时间", System.currentTimeMillis().toString())

        var temp: String
        for (i in 0 until arr.size - 1) {
            for (j in 0 until arr.size - i - 1) {
                val a =
                    (if (isContainChinese(arr[j])) PinYinUtil.getFirstSpell(arr[j]) else arr[j]).lowercase()
                val b =
                    (if (isContainChinese(arr[j + 1])) PinYinUtil.getFirstSpell(arr[j + 1]) else arr[j + 1]).lowercase()
                val result = compare(a, b)
                if (result > 0) {
                    temp = arr[j]
                    arr[j] = arr[j + 1]
                    arr[j + 1] = temp
                }
            }
        }
        Log.d("bubble排序开始时间", System.currentTimeMillis().toString())

        arr.forEachIndexed { index, s ->
            Log.i("序号$index：", s)
        }
    }

    /**
     * 快速排序
     */
    fun quickSort(arr: Array<String>) {
        Log.d("quick排序开始时间", System.currentTimeMillis().toString())
        handleQuickSort(arr, 0, arr.size - 1)
        Log.d("quick排序完成时间", System.currentTimeMillis().toString())
        arr.forEachIndexed { index, s ->
            Log.i("序号$index：", s)
        }
    }

    private fun handleQuickSort(arr: Array<String>, low: Int, high: Int) {
        if (low < high) {
            // 获取分区后的枢纽位置
            val pivotIndex = partition(arr, low, high)
            // 分别对枢纽左右两边的子数组进行递归排序
            handleQuickSort(arr, low, pivotIndex - 1)
            handleQuickSort(arr, pivotIndex + 1, high)
        }
    }

    private fun partition(arr: Array<String>, low: Int, high: Int): Int {
        // 选择数组的最后一个元素作为枢纽值
        val tempA = arr[high]
        val a =
            if (isContainChinese(tempA)) PinYinUtil.getFirstSpell(tempA) else tempA
        var i = low - 1

        // 遍历数组，将小于枢纽值的元素放到左边，大于枢纽值的元素放到右边
        for (j in low until high) {

            val tempB = arr[j]
            val b = if (isContainChinese(tempB)) PinYinUtil.getFirstSpell(tempB) else tempB

            val result = compare(a, b)
            if (result > 0) {
                i++
                // 交换 arr[i] 和 arr[j]
                val temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
            }
        }

        // 将枢纽元素放到正确的位置
        val temp = arr[i + 1]
        arr[i + 1] = arr[high]
        arr[high] = temp

        // 返回枢纽位置
        return i + 1
    }

    private fun compare(a: String, b: String): Int {
        var i = 0
        val tempA = (if (isContainChinese(a)) PinYinUtil.getFirstSpell(a) else a).lowercase()
        val tempB = (if (isContainChinese(b)) PinYinUtil.getFirstSpell(b) else b).lowercase()
        while (i < tempA.length && i < tempB.length && tempA[i] == tempB[i]) {
            i++
        }
        return if (i == tempA.length || i == tempB.length)
            tempA.compareTo(tempB)
        else tempA[i].code - tempB[i].code
    }

    /**
     * Arrays排序
     */
    fun arraysSort(array: Array<String>) {

        Log.d("Arrays排序开始时间", System.currentTimeMillis().toString())
        Arrays.sort(array) { a: String, b: String ->
            compare(a, b)
        }

        Log.d("Arrays排序完成时间", System.currentTimeMillis().toString())
        array.forEachIndexed { index, s ->
            Log.i("序号$index：", s)
        }

    }

    private fun isContainChinese(str: String): Boolean {
        val p: Pattern = Pattern.compile("[\u4e00-\u9fa5]")
        val m: Matcher = p.matcher(str)
        return m.find()
    }
}